home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 12479 < prev    next >
Encoding:
Text File  |  1996-08-05  |  4.4 KB  |  156 lines
  1. Path: tokyonet.ad.jp!wincgw1!senri-nc!odins-suita!aist-nara!wnoc-kyo-news!kuis-news!shamada
  2. From: shamada@kuis.kyoto-u.ac.jp (Shin-ichirou Hamada)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: newbie needs help
  5. Date: 20 Mar 1996 05:04:23 GMT
  6. Organization: Dept. of Information Science, Kyoto University, JAPAN
  7. Distribution: world
  8. Message-ID: <4io3kn$4gq@hemp.imel.kyoto-u.ac.jp>
  9. References: <$sjBUKACjrSxEw4g@waichung.demon.co.uk>
  10. NNTP-Posting-Host: goofy
  11. X-Newsreader: mnews [version 1.19] 1995-07/21(Fri)
  12. Originator: news@aladdin
  13.  
  14. In the article, newbie needs help, 
  15. kyn@waichung.demon.co.uk said as ">..."
  16.  
  17. Hello, My name is HAMADA Shin-ichirou.
  18. I am poor at English, but I want to do something to aid you( and want
  19. to talk with English-speakers), so I'm going to post this article.
  20.  
  21. #I'm sorry if there are any deviant representation.
  22.  
  23. >I require help in constructing a binary search tree in c++, as i am 
  24. >relatively new to the language i am not sure how to go about 
  25. >implementing it. 
  26.  
  27. I am also C++ beginner, but tries to think this subject on C++ together.
  28.  
  29. > struct node 
  30. >  {
  31. >   data  d;
  32. >   struct node  *left;
  33. >   struct node  *right;
  34. >  }
  35.  
  36. >if this is correct how do build a tree from this and insert words into 
  37. >it?
  38.  
  39. At first, let's divide this subject into class-user side and
  40. class-designing side to analyze requirement.
  41.  
  42. By later side, it is happy that a binary-tree is just like only an
  43. object (This course is same as list structure), which we call as
  44. btree-container class, in which entry and delete(Oh, this is needless,
  45. isn't it?) method of a node are prepared(Some methods for reading are
  46. necessary, but they are out of discussion in this time). These methods
  47. construct binary tree automatically.
  48.  
  49. Then, let's think about class designing on the basis of above points.
  50. we prepare two classes, that is to say, btree container class and
  51. btree node class.
  52.  
  53. Following is a sample of the classes;
  54.  
  55. class BTREE {
  56. private:
  57.   BT_NODE *root_node;
  58. public:
  59.   // constructor
  60.   BTREE() : root_node( NULL ){
  61.   }
  62.   // destructor
  63.   ~BTREE(){
  64.     delete root_node;
  65.   }
  66.   // entry method
  67.   void entry( DATA data ){
  68.     if( root_node == NULL ){
  69.       root_node = new BT_NODE( data );
  70.     } else {
  71.       root_node->add( data );
  72.     }
  73.   }
  74. }
  75.  
  76. class BT_NODE {
  77. private:
  78.   BT_NODE *left_node;
  79.   BT_NODE *right_node;
  80.   DATA _data;
  81.   cmp_data( DATA target, DATA current );
  82.   // private constructor
  83.   BT_NODE( DATA data )
  84.   : left_node( NULL ), right_node( NULL ), _data( data ) {
  85.   }
  86.   // private destructor
  87.   virtual ~BT_NODE(){
  88.     delete left_node;
  89.     delete right_node;
  90.   }
  91. public:
  92.   // recursive entry method
  93.   BT_NODE *add( DATA data ){
  94.     // You can make cmp_data() as you like.
  95.     // In this time, allowing duplication, no handle of zero.
  96.     // left side <= right side
  97.     if( cmp_data( data, _data ) < 0 ){
  98.       if( left_node != NULL ){
  99.         left_node->add( data );
  100.       } else {
  101.         left_node = new BT_NODE( data );
  102.       }
  103.     } else {
  104.       if( right_node != NULL ){
  105.         right_node->add( data );
  106.       } else {
  107.         right_node = new BT_NODE( data );
  108.     }
  109.   }   
  110. }
  111.  
  112. Following is a sample usage;
  113.  
  114. int main()
  115. {
  116.   BTREE btree;
  117.   DATA dat1;
  118.   DATA dat2;
  119.   DATA dat3;
  120.  
  121.   btree.entry( dat1 );
  122.   btree.entry( dat2 );
  123.   btree.entry( dat3 );
  124. }
  125.  
  126. I explain above program.
  127. You can make binery-tree if you only send a message "entry( dat )" to
  128. an BTREE object..Perhaps(^^;
  129.  
  130. At first, this message reach BTREE object, then if root_node is NULL,
  131. the data are entered on root_node and processing is completed. If
  132. root_node isn't NULL, a message "add( dat )" are sent to root_node.
  133. If a node object receive this message, he compare dat in the massage
  134. with his dat, and will pass the message to the left( or right ) side
  135. node object, when if destination object doesn't exist( that is to say,
  136. left( or right ) side pointer is NULL ), the dat will be registered as
  137. a new node there.
  138.  
  139. >The following is how i would implement a binary search tree in pascal.
  140. >Your help will be much appreciated.
  141. >BTW i mostly program in pascal but i felt that i needed to learn other
  142. >languages.
  143. #what is BTW??
  144. Sorry, I am not well acquainted with Pascal.
  145.  
  146. Good bye.
  147.  
  148.  
  149. --
  150.                                                                 
  151.  \----%@  Doushita Lab., Information Science Cource,
  152.   \  /       Technology Department, Kyoto Univ.                                
  153.    \/         
  154.    $B!C(B             HAMADA, Shin-ichirou
  155.    $B!1(B                                                          
  156.